package com.leecode;

import com.test.TreeNode;
import sun.reflect.generics.tree.Tree;

/**
 * 98. 验证二叉搜索树
 * <p>
 * 给定一个二叉树，判断其是否是一个有效的二叉搜索树。
 * <p>
 * 假设一个二叉搜索树具有如下特征：
 * <p>
 * 节点的左子树只包含小于当前节点的数。
 * 节点的右子树只包含大于当前节点的数。
 * 所有左子树和右子树自身必须也是二叉搜索树。
 * <p>
 * 示例 1:
 * <p>
 * 输入:
 * 2
 * / \
 * 1   3
 * 输出: true
 */
public class Leet98 {
	public static void main(String[] args) {
//		TreeNode treeNode = new TreeNode();
//		TreeNode<Integer> integerTreeNode = new TreeNode<>(5, new TreeNode<>(1), new TreeNode<>(4, new TreeNode<>(3), new TreeNode<>(6)));
		TreeNode<Integer> integerTreeNode = new TreeNode(-3, new TreeNode(1, new TreeNode(0), new TreeNode(2, null, new TreeNode(3))), null);
		new Leet98().isValidBST(integerTreeNode);
	}

	/**
	 * 32%,17%,我之前:dfs遍历所有,中序add到list中,list遍历检查是否有前>后的,有就返false
	 * 考点:"从左子根开始中序遍历,一个比一个大"
	 */
		Integer pre=Integer.MIN_VALUE;
	public boolean isValidBST(TreeNode<Integer> root) {
//		return recur(root, null, null);//solve1

		if(root==null){
			return true;
		}
		if (!isValidBST(root.left)) {
			return false;
		}
		if (root.val <= pre) {
			return false;
		}
		pre=root.val;
		return isValidBST(root.right);


//		return true;
	}

	/**
	 * 35%,79%,我想出左右界后,艰难改bug,最后成功还是35%???????????????!!!!!!!!!!!!!!就优化了空间?时间几乎没优化?!!!!!!!
	 * bug:单纯比较left和mid和right不行,
	 * bug2:
	 * bug3:一味追求代码的行数少,条件写的把自己都绕进去了!!
	 * 考点:
	 * @param ll 左界
	 * @param rr 右界
	 */
	public boolean recur(TreeNode<Integer> root, Integer ll, Integer rr) {
		if (root == null) return true;
		if (root.left == null && root.right == null) {
			if ((ll == null ? true : ll < root.val) && (rr == null ? true : root.val < rr)) {
				return true;//bug3:漏写ll < root.val && root.val < rr
			}
		}
		if (root.left != null && root.right == null && root.left.val < root.val) return recur(root.left, ll, root.val);//bug:ll写成null
		if (root.left == null && root.right != null && root.val < root.right.val) return recur(root.right, root.val, rr);//bug:rr写成null
		if (root.left != null && root.right != null && root.left.val < root.val && root.val < root.right.val) {
			if ((ll == null ? true : ll < root.left.val) && (rr == null ? true : root.right.val < rr)) {
				return recur(root.left, ll, root.val) && recur(root.right, root.val, rr);//bug2:ll,rr总是在"脑海模拟第一次的时候"写成null
			}
		}

		return false;
	}

}
